7、基德的密码锁

题目 基德的密码锁

思路分析

第一眼也是发现可以用指数型枚举dfs去写

但是数据范围是1000 那明显就是要把dfs改成dp了

状态表示：第i个位置 选j的方案总数

属性：count

状态计算：上一个数 选1~j-k 和 j+k~m的方案数之和

只能过1/3 6分

优化暂时没想到

可能可以用前缀和 但是结合在dp过程中 代码难度就上去了 不敢保证写对 可能全改错了 不值得冒这个风险

代码实现

朴素 5/15

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

//感觉可以指数型枚举的写法 但是数据范围是1000 那应该是dfs改dp

const int N=1010,M=5010,mod=998244353;

LL f[N][M];//第i个位置 选j的方案总数 count

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n,m,k;

    cin>>n>>m>>k;

    for(int i=1;i<=m;i++)

        f[1][i]=1;//第一个位置可以选任何数 有一种方案

    for(int i=2;i<=n;i++){

        for(int j=1;j<=m;j++){

            if(j-k>=1){

                for(int c=1;c<=j-k;c++){

                    f[i][j]=(f[i][j]+f[i-1][c])%mod;

                }

            }

            if(j+k<=m){

                for(int c=j+k;c<=m;c++){

                    f[i][j]=(f[i][j]+f[i-1][c])%mod;

                }

            }

        }

    }

    LL res=0;

    for(int i=1;i<=m;i++){

        res=(res+f[n][i])%mod;

    }

    cout<<res;

    return 0;

}

前缀和优化 ac

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=1010,M=5010,mod=998244353;

LL f[N][M];

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n,m,k;

    cin>>n>>m>>k;

    for(int i=1;i<=m;i++)

        f[1][i]=1;

    for(int i=2;i<=n;i++){

    	for(int j=1;j<=m;j++)

    		f[i-1][j]=(f[i-1][j]+f[i-1][j-1])%mod;

        for(int j=1;j<=m;j++){

            if(j-k>=0)

                f[i][j]=(f[i][j]+f[i-1][j-k])%mod;

            if(k==0)

            	f[i][j]=(f[i][j]+f[i-1][m]-f[i-1][min(m,j+k)]+mod)%mod;

            else

                f[i][j]=(f[i][j]+f[i-1][m]-f[i-1][min(m,j+k-1)]+mod)%mod;

            f[i][j]%=mod;

        }

    }

    LL res=0;

    for(int i=1;i<=m;i++){

        res=(res+f[n][i])%mod;

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 6、七彩之城的独特序列 🏠 00-刷题理模型 ➡️ 8、完美队列的数目